//35. 搜索插入位置
//思路：遍历每一个数，与给定值作比较，如何相等就返回这个位置
//如果不存在这个值，就用遍历来比较哪个数大于给定值，这个数的位置就是要插入的位置
//除上面两种情况外，就返回最后一个位置
//int searchInsert(int* nums, int numsSize, int target)
//{
//    int i = 0;
//    for (i = 0; i < numsSize; i++)
//    {
//        if (nums[i] == target)
//            return i;
//    }
//    for (i = 0; i < numsSize; i++)
//    {
//        if (target < nums[i])
//            return i;
//    }
//    return numsSize;
//}


//思路：因为需要查找的时间复杂度是O(NlogN)，这里暗示用二分查找
//二分查找是在数组中找到 target，但是这里多出来了一个条件，不存在的时候找到应该插入的位置
//target的位置应该在的区间：nums[i-1] < target <= nums[i]
//我们使用一个变量用来保存下标，初始化为numsSize，因为存在一种情况，target大于数组所有元素

int searchInsert(int* nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;
    int ret = 0;
    while (left < right)
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target)
        {
            left = mid + 1;
        }
        else if (target <= nums[mid])
        {
            ret = mid;
            right = mid - 1;
        }
    }
    return ret;
}